package xiaomin.demo.algorithm;
/*
给定 一个 二维 的 m × n 矩阵，
如果 某个 元素 为 0，
那么 将其 所 在行 和 列 的 所有 元素 设为 0。
不允许 使用 额外 空间。

陈东锋. 进军硅谷:程序员面试揭秘 (技术移民参考手册) (p. 95). 电子工业出版社. Kindle 版本.

//思路，
1.找到第一个0,利用该0所在的行和列作为存储,记录该坐标x,y
2.遍历整个矩阵,如果某一个数为零,记录该数的下标,在存储区对应的两个数置为0
如下图所示
            {1,0,3,4},
            {5,6,0,8},
            {9,10,11,12}

            {1,0,0,4},
            {5,0,0,8},
            {9,10,11,12}
3.遍历存储区的行(忽略中心点),当遇到0时,该矩阵整个列变为0
            {1,0, 0, 4},
            {5,0 ,0, 8},
            {9,10,0,12}
4.遍历存储区的列(忽略中心点),当遇到0时,该矩阵整个行变为0
            {1,0, 0, 4},
            {0,0 ,0, 0},
            {9,10,0,12}
5.把x,y所在的行列都变0
            {0,0, 0, 0},
            {0,0 ,0, 0},
            {9,0, 0,12}
 */
public class Lesson24 {
    public static void run(){
        int[][] matrix ={
            {1,0,3,4},
            {5,6,0,8},
            {9,10,11,12}
        };

        int x=-1,y=-1;

        //记录第一个0的坐标
        for(int i=0;i< matrix.length;i++){
            for(int j=0;j<matrix[i].length;j++){
                if(matrix[i][j]==0){
                    x=j;
                    y=i;
                    break;
                }
            }
            if(x!=-1)
                break;
        }

        //标记
        for(int i=0;i< matrix.length;i++){
            for(int j=0;j<matrix[i].length;j++){
                if(matrix[i][j]==0){//
                    matrix[y][j]=0;
                    matrix[i][x]=0;
                }
            }
        }

        for(int i=0;i<matrix.length;i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }

        //遍历竖向数组
        for(int i=0;i<matrix.length;i++){
            if(i!=y && matrix[i][x]==0) {
                //整行都是0
                for (int j = 0; j < matrix[i].length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        //遍历横向数组
        for(int i=0;i<matrix[y].length;i++){//
            if(i!=x && matrix[y][i]==0){
                //整列都是0
                for(int j=0;j<matrix.length;j++){
                    matrix[j][i] = 0;
                }
            }
        }
        //整列都变0
        for(int i=0;i<matrix.length;i++){
            matrix[i][x]=0;
        }
        //整行都变0
        for(int i=0;i<matrix[y].length;i++){
            matrix[y][i]=0;
        }

        for(int i=0;i<matrix.length;i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}
